Distributed data storage systems, such as those used in cloud computing environments, typically store any given data item in a plurality of locations to ensure data durability. These locations comprise disks stored on server replicas of the distributed data storage systems and are typically mapped to the data items using some form of storage assignment mappings, such as a table. Such storage assignment mappings often associate a specific number of disks with each data item (e.g., three disks mapped to a data item).
To increase overall throughput of the system, it is often desirable to add to the system to increase the total number of disks involved in read and write operations. Adding disks typically involves redistributing data items among the existing and new disks of the system. One technique for redistributing data items involves selecting a set of data items to be stored on a new disk and associating the new disk with those data items in the storage assignment mappings. The storage assignment mappings are then updated to remove a disk previously assigned to each data item and replace that disk in the storage assignment mappings with the new disk. Because each data item associated with the new disk may be associated with a different set of disks, the new disk may only replace the removed disks with respect to one or more data items. The “removed” disks may remain part of the system and the storage assignment mappings with respect to other data items. Upon accepting their storage assignments, the new disks retrieve the data items from the other disks storing those data items.
One issue with this technique is that it results in a temporary decrease in data durability. In the time it takes for the new disk to retrieve and store the data items associated with it, the system is under-replicated with respect to those data items. This decrease in data durability may increase data loss or the cost of data recovery in the event of disk failures.